package arithmetic.demo5;

import java.util.*;

/**
 * 问题: 记忆化搜索_最长递增子序列
 */

class Solution6 {


    public int lengthOfLIS(int[] nums) {
        // 初始化
        int n = nums.length;


        int ret = 0;

        int[] memo = new int[n];

        // 开始记忆化搜索
        for(int i = 0; i < n ; i++) {
            ret =  Math.max(ret,dfs(nums,i, memo));
        }


        return ret;
    }


    private  int dfs(int[] nums , int pos, int[] memo) {

        // 递归出口
        if(memo[pos] != 0) {
            return memo[pos];
        }


        int ret = 1;
        // 查找到更小的值
        for(int i = pos - 1; i >= 0 ; i--) {
            if(nums[pos] > nums[i]) {
                ret = Math.max(ret,dfs(nums , i ,memo) + 1);
            }
        }

        memo[pos] = ret;
        return ret;
    }

}

/**
 * 题目： 动态规划_最长递增子序列
 */

class Solution7 {


    public int lengthOfLIS(int[] nums) {

        

        // 初始化
        int n = nums.length;


        int ret = 0;

        int[] dp = new int[n];



        // 初始化
        Arrays.fill(dp,1);



        // 从后往前是模仿回溯的时候
        for(int i = n-1; i >= 0  ; i--) {
            // 从起始 i 的后一位开始寻找比它大的数
            for(int j = i + 1; j<n ; j++) {
                if(nums[i] < nums[j]) {
                    // 状态转移
                    // 找出从 i 开始， 和 dp[j] + 1 的下一层
                    dp[i] = Math.max(dp[i], dp[j] + 1);

                }

            }

            // 最后遍历查找出 dp 表中的最大的长度
            ret = Math.max(ret, dp[i]);
        }




        return ret;
    }



}


/**
 * 题目： 记忆化搜索_猜数字大小（2）
 */

class Solution8 {
    int n;
    int ret ;


    public int getMoneyAmount(int _n) {
        n = _n;
        ret =0;

        // 进行记忆化搜索
        int[][] memo = new int[n+1][n+1];

        return dfs(1,n,memo);
    }

    // 进行左右区间 dfs 
    private int dfs(int left , int right, int[][]memo ) {
        // 递归出口
        if(left >= right) {
            return 0;
        }

        // 使用备忘录
        if(memo[left][right] != 0) {
            return memo[left][right];
        }


        int ret = Integer.MAX_VALUE;
        for(int i = left; i <= right ; i++) {

            // 得到两边区间的值
            int x = dfs(left, i - 1,memo);
            int y = dfs(i+1, right,memo);

            // 从两边区间中得到都能满足各自条件的最大值
            int tmp = Math.max(x, y) + i;

            // 最终把所有可能的暴搜的情况返回
            ret = Math.min(tmp, ret);
        }

        // 加入备忘录
        memo[left][right] = ret;

        return ret;

    }
}


/**
 * 题目： 记忆化搜索_矩阵中的最长递增路径
 */

class Solution {
    int[] dx= {0,0,-1,1};
    int[] dy = {-1,1,0,0};

    int row , col ;

    public int longestIncreasingPath(int[][] matrix) {
        // 长 和 宽
        row = matrix.length;
        col = matrix[0].length;
        int ret =0;

        // 备忘录
        int[][] memo = new int[row][col];

        for(int i =0; i < row ; i++) {
            for(int j = 0; j < col ; j++) {
                // 从起点开始
                ret = Math.max(ret,dfs(matrix,i,j,memo));
            }
        }
        return  ret;
    }

    private int dfs(int[][] nums, int r, int c, int[][] memo) {

        // 使用备忘录
        if(memo[r][c] != 0) {
            return memo[r][c];
        }

        int ret = 1;
        for(int i =0; i<4; i++) {
            int x = r + dx[i];
            int y = c + dy[i];

            // 剪枝
            if(x>= 0 && x<row && y>= 0 && y<col && nums[r][c] < nums[x][y]) {
                ret = Math.max(ret,dfs(nums,x,y,memo) + 1);
            }
        }



        // 加入备忘录
        memo[r][c] = ret;
        return ret;
    }



}


/**
 * 题目： 排序_颜色分类
 */

class Solution1 {
    public void sortColors(int[] nums) {

        // 计数排序
        int n = nums.length;
        int[] hash= new int[3];
        // 统计
        for(int i=0; i<n ; i++) {
            int num =  nums[i];
            hash[num]++;
        }

        // 重新放入数组中
        int j =0;
        for(int i =0; i<3; i++) {
            while(hash[i] != 0) {
                nums[j] = i;
                hash[i]--;
                j++;
            }
        }

    }
}


/**
 * 题目： 快速排序_颜色分类
 */

class Solution2 {

    // 双指针排序
    public void sortColors(int[] nums) {
        int n = nums.length;
        int left = -1, right = n ;
        int i=0;
        while(i != right) {
            if(nums[i] == 0) {
                left++;
                swap(nums,left, i);
                i++;
            } else if(nums[i] == 1) {
                i++;
            } else {
                right--;
                swap(nums, i, right);
            }
        }

    }

    // 交换
    private void swap(int[] nums, int x , int y) {
        int tmp = nums[x];
        nums[x] = nums[y];
        nums[y] = tmp;
    }
}




class Solution4 {


    // 快速排序
    public int[] sortArray(int[] nums) {
        int n = nums.length;




        // 开始递归
        quickSort( nums ,0, n - 1);

        return nums;
    }

    private void quickSort(int[] nums, int left , int right) {
        // 递归出口
        if(left >= right) {
            return;
        }

        Random r = new Random();
        int index =  r.nextInt(right - left + 1)  + left;
        int key = nums[index];
        int begin = left -1,  end = right +1 , i = left;

        // 开始数组三段法
        while(i < end) {
            if(nums[i] > key) {
                swap(nums, --end, i);
            } else if(nums[i] == key) {
                i++;
            } else {
                swap(nums, ++begin , i++);
            }
        }

        Random r1 = new Random();



        quickSort(nums, left, begin);

        quickSort(nums, end ,right);
    }



    // 交换
    private void swap(int[] nums , int i , int j ) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

}
